package com.example.arithmeticleetcode.learnArithmetic2.sort;

/**
 * @program: arithmetic-leetcode
 * @description: 插入排序 最好的时间复杂度 O(n) 最坏 平均复杂度O(n^2)  空间复杂度 O(1)  稳定排序
 * @author: FangZhen
 * @create: 2020-11-05 17:09
 **/
public class InsertionSort3<E extends Comparable<E>> extends Sort<E> {

    @Override
    protected void sort() {
        for (int begin = 1, len = array.length; begin < len; begin++) {
            insert(begin, search(begin));
        }
    }

    /**
     * 将source位置的元素插入到dest位置
     *
     * @param source
     * @param dest
     */
    private void insert(int source, int dest) {
        E v = array[source];
        for (int i = source; i > dest; i--) {
            array[i] = array[i - 1];
        }
//        System.arraycopy(array, dest, array, dest + 1, source - dest);
        array[dest] = v;
    }

    /**
     * 利用二分查找找到index位置元素的插入位置
     *      已经排好序数组的区间范围是[0, index)
     * @param index
     * @return
     */
    private int search(int index) {
        E v = array[index];
        int begin = 0;
        int end = index;
        while (begin < end) {
            int mid = (begin + end) >> 1;
            if (cmp(v, array[mid]) < 0) {
                end = mid;
            } else {
                begin = mid + 1;
            }
        }
        return begin;

    }
}
